<html>

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 
  <link rel="stylesheet" title="Default" href="http://acm.math.spbu.ru/~sk1/colorer/my.css">

  <script src="http://acm.math.spbu.ru/~sk1/colorer/highlight.js"></script>
  <script src="http://acm.math.spbu.ru/~sk1/colorer/cpp.js"></script>
  <script>hljs.initHighlightingOnLoad();</script>
</head>

<body>

<pre><code>
typedef vector &lt;pnt&gt; vpnt;

inline bool pless( const pnt &a, const pnt &b )
{
  ll x = a * b;
  return x != 0 ? x &lt; 0 : a.d2() &lt; b.d2();
}

vpnt ConvexHull( vpnt p )
{
  int n = sz(p), mi = 0;
  assert(n &gt; 0);
  forn(i, n)
    if (p[mi] &lt; p[i])
      mi = i;
  swap(p[0], p[mi]);
  forab(i, 1, n - 1)
    p[i] = p[i] - p[0];
  sort(p.begin() + 1, p.end(), pless);

  int rn = 0;
  vpnt r(n);
  r[rn++] = p[0];
  forab(i, 1, n - 1)
  {
    pnt q = p[i] + p[0];
    while (rn &gt;= 2 && (r[rn - 1] - r[rn - 2]) * (q - r[rn - 2]) &gt;= 0)
      rn--;
    r[rn++] = q;
  }
  r.resize(rn);
  return r;
}

</code></pre>

</body>
</html>

<font style="visibility:hidden">
